'''
https://leetcode.cn/problems/n-queens/
'''
from typing import List


class Solution:
    def totalNQueens(self, n: int) -> int:
        def process(row, path):
            if row == n:
                return 1
            ans = 0
            for col in range(n):
                flag = True
                for pre_row in range(row):
                    pre_col = path[pre_row]
                    if col == pre_col:
                        flag = False
                        break
                    if abs(row - pre_row) == abs(col - pre_col):
                        flag = False
                        break
                if flag:
                    path.append(col)
                    ans += process(row + 1, path)
                    path.pop()
            return ans
        return process(0, [])




    def solveNQueens(self, n: int) -> List[List[str]]:
        ans = []
        template = '.' * n
        def process(row, path):
            if row == n:
                ans.append( [template[0:col] + 'Q' + template[col+1:] for col in path])
                return
            for col in range(n):
                flag = True
                for pre_row in range(row):
                    pre_col = path[pre_row]
                    if col == pre_col:
                        flag = False
                        break
                    if abs(row - pre_row) == abs(col - pre_col):
                        flag = False
                        break
                if flag:
                    path.append(col)
                    process(row + 1, path)
                    path.pop()
        process(0, [])
        return ans

